/******************************************************************************
 *  Date:
 *      March 2011
 *
 *  Authors:
 *      Tomasz Jankowski 171073
 *
 *  Puprose:
 *      An academic project on Univercity of technologi in Wroclaw.
 *
 ******************************************************************************/
 
#ifndef GRAPH_GENERATOR_HPP
#define GRAPH_GENERATOR_HPP

#include "vector.hpp"
#include "list.hpp"

/* *** Opis klas i metod ***
 *
 *  Graph - abstrakcyjna klasa reprezentujaca bardziej matematyczne pojecie
 *          grafu. Implementacje tej klasy abstrakcyjnej nie dopuszczaja grafow
 *          z cyklami i wielokrotnymi krawedziami.
 *
 *      generate() - generuje losowy graf
 *      print() - wyswietla graf w konsoli 
 *
 *  IncidenceMatrix - abstrakcyjna klasa grafu w postaci macierzy incydencji
 *
 *  UnorientedIncidenceMatrix - graf nieskierowany w postaci macierzy incydencji
 *
 *  OrientedIncidenceMatrix - graf skierowany w postaci macierzy incydencji
 *
 *  Adjacencylist - abstrakcyjna klasa grafu w postaci list sasiedztwa
 *
 *  UnorientedAdjacencyList - graf nieskierowany w postaci listy sasiedztwa
 *
 *  OrientedAdjacencyList - graf skierowany w postaci listy sasiedztwa
 */

using namespace std;
 
class Graph 
{
    public:  
        virtual void generate (unsigned int minimum_edge_weight,
                               unsigned int maximum_edge_weight) = 0;
        virtual void print (void) = 0;
        
    protected:
        Graph (unsigned int nodes,
               unsigned int edges);
               
        const unsigned int nodes;
        const unsigned int edges;
};

class IncidenceMatrix :
    public Graph
{
    public:                              
        virtual ~IncidenceMatrix (void);
                       
        void print (void);
        
    protected:
        IncidenceMatrix (unsigned int nodes,
                         unsigned int edges);
                         
        bool check_nodes (unsigned int begin_node,
                          unsigned int end_node);                 
                          
        int** matrix;
};

class OrientedIncidenceMatrix :
    public IncidenceMatrix
{
    public:
        OrientedIncidenceMatrix (unsigned int nodes,
                                 unsigned int edges);
                         
        void generate (unsigned int minimum_edge_weight,
                       unsigned int maximum_edge_weight);
                       
        void find_shortest_path_dijkstra (unsigned int source_node);       
        void find_shortest_path_bellman_ford (unsigned int source_node);     
};

class UnorientedIncidenceMatrix :
    public IncidenceMatrix
{
    public:
        UnorientedIncidenceMatrix (unsigned int nodes,
                                   unsigned int edges);
                         
        void generate (unsigned int minimum_edge_weight,
                       unsigned int maximum_edge_weight);
                       
        UnorientedIncidenceMatrix get_spanning_tree_prim (void);
        UnorientedIncidenceMatrix get_spanning_tree_kruskal (void);   
        
	private:
		struct wagi
		{
			int waga;
			int krawedz;
			int wierzcholek_pocz;
			int wierzcholek_koniec;
		};
		
		void sortowanie(wagi tab[], int lewy, int prawy);
		int findSet(int x, int *p);
		void link(int x, int y, int *p, int *rank);
		void polacz(int x, int y, int *p, int *rank);             
};

class Adjacencylist :
    public Graph
{
    public:                                
        virtual ~Adjacencylist (void); 
                       
        void print (void);
        
    protected:          
        struct Neighbour
        {
            Neighbour (unsigned int node,
                       unsigned int edge_weight);
                       
            const unsigned int node;
            const unsigned int edge_weight;
        };
        
        typedef List<Neighbour>            NodeNeighboursList;
        typedef Vector<NodeNeighboursList> NodesVector;
        
        Adjacencylist (unsigned int nodes,
                       unsigned int edges); 
        
        bool check_nodes (unsigned int begin_node,
                          unsigned int end_node);
    
        NodesVector nodes_vector;
};

class OrientedAdjacencyList :
    public Adjacencylist
{
    public:
        OrientedAdjacencyList (unsigned int nodes,
                               unsigned int edges);
                         
        void generate (unsigned int minimum_edge_weight,
                       unsigned int maximum_edge_weight);     
                       
        void find_shortest_path_dijkstra (unsigned int source_node);            
        void find_shortest_path_bellman_ford (unsigned int source_node);     
};

class UnorientedAdjacencyList :
    public Adjacencylist
{
    public:
        UnorientedAdjacencyList (unsigned int nodes,
                                   unsigned int edges);
                         
        void generate (unsigned int minimum_edge_weight,
                       unsigned int maximum_edge_weight);
                       
        UnorientedAdjacencyList get_spanning_tree_prim (void);
        UnorientedAdjacencyList get_spanning_tree_kruskal (void);    
        
    private:
        struct wagi
		{
			int waga;
			int krawedz;
			int wierzcholek_pocz;
			int wierzcholek_koniec;
		};
		
		void sortowanie(wagi tab[], int lewy, int prawy);
		int findSet(int x, int *p);
		void link(int x, int y, int *p, int *rank);
		void polacz(int x, int y, int *p, int *rank);                      
};

#endif // GRAPH_GENERATOR_HPP
